BSGS (Baby Steps Giant Steps)从入门到入土
BSGS (Baby Steps Giant Steps)从入门到入土
1.BSGS
求解如关于$x$的方程$A^x≡B \mod p$ 的最小整数解。$(A,p互质,p为质数)$
不难发现$x<=p$ 因为会出现循环。
靠虑将$x$分解为$i\times sqrt(x)-j$ 。
则原式化为$A^{i\times \lceil sqrt(x)\rceil}\times A^{-j}≡B \mod p$
对$A^{-j}$求逆元得$A^{i\times \lceil sqrt(x)\rceil}≡B\times A^j \mod p$
因为可以求一个同余方程$A^{-j}\times inv_{A^{-j}}≡1 mod p$
显而易见$inv_{A^{-j}}$即为$A^j$ ,其实有点像移项,可惜$p$不与$A$互质移不过来,可能导致左边$mod p$后为$0$
然后可知在$mod p$的意义下左右两式相等。
所以就可以用$map$吧左右的值映射成它的指数,先做右边($j$从$0$枚举到$\lceil sqrt(x)\rceil$),并把每次的$j$映射到$map$以$B\times A^j$为下标的空间中。然后做左边($i$从$1$枚举到$ \lceil sqrt(x)\rceil$),每次查表搞一搞,第一次遇到相同的值就可以拿现在的$i\times \lceil sqrt(x)\rceil$与表中的$j$相减即为最小值,因为此时$i\times \lceil sqrt(x)\rceil$最小,$j$最大。
理论时间复杂度为$O(sqrt(p))$,但由于用了$map$所以多了红黑树查值的复杂度,所以多了个$log$。
代码
1 |
|
2.exBSGS
若$A,p$不互质,那普通的$BSGS$就难以胜任了,所以需要使用$exBSGS$
其实也很简单,假设$t=gcd(A,p)$,则可推出$A^{x-1}\times \frac{A}{t}≡\frac{B}{t} \mod p$
若$t\nmid B$,则只有$B=1$时有$x=0$的最小解
若$t \mid b $,则当$t=1$时用$BSGS$,求解即可。
反复执行,直至$A,p$互质。
最后,若此过程需要反复进行$k$次,则答案为$BSGS$的解$x+k$。
代码
1 |
|